public class ListNode {
        int val;
        ListNode next;

        ListNode head;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    public ListNode removeElements(ListNode head, int val) {



                if(head==null){
                    return null;
                }
                ListNode cur=head;
                ListNode curN=head;
                while(curN.next!=null){
                    cur=curN.next;
                    if(cur.val==val){
                        curN.next=cur.next;
                    }else{
                        curN=curN.next;
                    }
                }
                if(head.val==val){
                    return head.next;
                }
                return head;

    }
    /**
     * 判断链表是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    return true;
                }
            }
            return false;
    }
    /**
     * 判断两链表是否有交点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int lenA=size(headA);
            int lenB=size(headB);
            ListNode curA=headA;
            ListNode curB=headB;

            if(lenA>lenB){
                while(lenA-lenB!=0){
                    curA=curA.next;
                    lenA--;
                }
            }else{
                while(lenB-lenA!=0){
                    curB=curB.next;
                    lenB--;
                }
            }
            while(curA!=null&&curB!=null){
             if(curA==curB){
                 return curA;
             }
                    curA=curA.next;
                    curB=curB.next;

            }
            return null;

    }

    /**
     * 判断是否为回文链表
     * @return
     */
    public boolean chkPalindrome() {
        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;

        }
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;

        }
        return true;
    }
    /**
     * 小于x在前，大于x在后，合成新链表
     * @param pHead
     * @param x
     * @return
     */
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode cur=pHead;
        ListNode bhead=null;
        ListNode bcur=null;
        ListNode ahead=null;
        ListNode acur=null;
        while(cur!=null){
            if(cur.val<x){
                if(bhead==null){
                    bhead=cur;
                    bcur=cur;
                }else{
                    bcur.next=cur;
                    bcur=bcur.next;
                }
                cur=cur.next;
            }else{
                if(ahead==null){
                    ahead=cur;
                    acur=cur;
                }else{
                    acur.next=cur;
                    acur=acur.next;
                }
                cur=cur.next;
            }
        }
        if(bcur==null){
            return ahead;
        }
        bcur.next=ahead;

        if(ahead!=null){
            acur.next=null;
        }
        return bhead;
    }
    /**
     * 合并两个升序链表
     * @param head1
     * @param head2
     * @return
     */
        public ListNode mergeTwoLists(ListNode head1,ListNode head2){
          ListNode nhead=new ListNode();
          ListNode cur=nhead;
          while(head1!=null&&head2!=null){
              if(head1.val<head2.val){
                  cur.next=head1;
                  cur=cur.next;
                  head1=head1.next;
              }else{
                  cur.next=head2;
                  cur=cur.next;
                  head2=head2.next;
              }
          }
          if(head2==null){
              while(head1!=null){
                  cur.next=head1;
                  cur=cur.next;
                  head1=head1.next;
              }

          }else{
              while(head2!=null){
                  cur.next=head2;
                  cur=cur.next;
                  head2=head2.next;
              }
          }
          return nhead;

        }

    /**
     * 返回倒数第K个节点的值,快慢指针
     * @param head
     * @param k
     * @return
     */
    public int kthToLast(ListNode head, int k) {
        ListNode fast=head;
        ListNode slow=head;
        --k;
        while(k!=0){
            fast=fast.next;
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
//    public int kthToLast(ListNode head, int k) {
//        int m=size(head)-k;
//        ListNode cur=head;
//        while(m!=0){
//            cur=cur.next;
//            m--;
//        }
//        return cur.val;
//    }

    /**
     * 计算节点个数
     * @param head
     * @return
     */
    public int size(ListNode head){
        ListNode cur=head;
        int count=0;

        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    /**
     * 返回中间节点,快慢指针
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

}
